package org.leetcode.easy.leetcode144;

import org.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

public class Solution
{
    /**
     * 递归前序遍历
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal(TreeNode root) {

        List<Integer> result = new ArrayList<>();

        preorder(root,result);

        return result;
    }

    public void preorder(TreeNode node,List<Integer> list)
    {
        if (node==null)  return;

        list.add(node.val);

        preorder(node.left,list);

        preorder(node.right,list);

    }

    /**
     * 迭代 前序遍历
     */

    public static List<Integer> preorderTraversal2(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return result;
    }

    /**
     * 迭代 中序遍历
     */
    public static List<Integer> preorderTraversal3(TreeNode root)
    {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
            if (cur != null){
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.pop();
                result.add(cur.val);
                cur = cur.right;
            }
        }
        return result;
    }

    /**
     * 迭代 后序遍历
     */

    public static List<Integer> preorderTraversal4(TreeNode root)
    {
        List<Integer> result = new ArrayList<>();

        if (root==null)
        {
            return result;
        }

        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);

        while (!stack.isEmpty())
        {
            TreeNode node = stack.pop();

            result.add(node.val);

            if (node.left!=null)
            {
                stack.push(node.left);
            }

            if (node.right!=null)
            {
                stack.push(node.right);
            }
        }

        Collections.reverse(result);

        return result;
    }


    public static void main(String[] args) {
        TreeNode node9 = new TreeNode(9);
        TreeNode node8 = new TreeNode(8);
        TreeNode node7 = new TreeNode(7);
        TreeNode node6 = new TreeNode(6);
        TreeNode node5 = new TreeNode(5, node8, node9);
        TreeNode node4 = new TreeNode(4);
        TreeNode node3 = new TreeNode(3, node6, node7);
        TreeNode node2 = new TreeNode(2, node4, node5);
        TreeNode node1 = new TreeNode(1, node2, node3); // 根节点

        List<Integer> integers = preorderTraversal3(node1);
    }
}
